package E_2024;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/*
【第k个排列】
    给定参数n，从1到n会有n个整数：1,2，3，...,n，这n个数字共有n！种排列。
    按大小顺序升序列出所有排列情况，并一一标记，当n=3时，所有排列如下：
    "123"
    "132"
    "213"
    "231"
    "312"
    "321"
    给定n和k，返回第k个排列。
输入描述：
    输入两行，第一行为n，第二行为k，给定n的范围是[1，9]，给定k的范围是[1，n!]。
输出描述：
    输出排在第k位置的数字。
示例1：
    输入：
    3
    3
    输出：
    213
    输入：
    4
    4
    1234 1243 1324 1342 1423 1432 2134
    由上述可知，第一位可由 k % (n-1)! 得到下标
 */
public class E_100_56 {
    public static void main(String[] args) {
        System.out.println(ans1(4,7));
        System.out.println(ans1(3,4));
        System.out.println(ans1(8,2));
    }
    public static String ans1(int n, int k){
        int temp = 1;
        for (int i = 1; i < n; i++) {
            temp += temp*i;
        }
        List<Integer> m = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            m.add(i+1);
        }
        StringBuilder ans = new StringBuilder();
        // 数据从下标0开始，因此k-1才是目标
        --k;
        while(n > 0){
            temp = temp/n--;
            ans.append(m.remove(k/temp));
            k = k % temp;
        }
        return ans.toString();
    }
    public static String ans(int n, int index){
        int[] temp = new int[n];
        temp[n-1] = 1;
        for (int i = n-2; i >= 0 ; i--) {
            temp[i] = (n-i)*temp[i+1];
        }
        System.out.println(Arrays.toString(temp));
        int[] m = new int[n];
        for (int i = 0; i < n; i++) {
            m[i] = i+1;
        }
        System.out.println(Arrays.toString(m));
        StringBuilder ans = new StringBuilder();
        int x = 1;
        while(x < n){
            int i = index == temp[x] ? 0 : index / temp[x];
            for (int j = 0; j < n && i > -1; j++) {
                if (m[j] == 0) continue;
                if (i == 0){
                    ans.append(m[j]);
                    m[j] = 0;
                }
                i--;
            }
            index = index % temp[x] == 0 ? 1 : index % temp[x];
            x++;
        }
        return ans.toString();
    }
}
